/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import org.jheaps.annotations.LinearTime

/**
 * An array based binary heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The implementation uses an array in order to store the elements and
 * automatically maintains the size of the array much like a
 * [java.util.Vector] does, providing amortized O(log(n)) time cost for
 * the `insert` and `deleteMin` operations. Operation
 * `findMin`, is a worst-case O(1) operation. The bounds are worst-case if
 * the user initializes the heap with a capacity larger or equal to the total
 * number of elements that are going to be inserted into the heap.
 *
 *
 *
 * Constructing such a heap from an array of elements can be performed using the
 * method [.heapify] or [.heapify]
 * in linear time.
 *
 *
 *
 * Note that the ordering maintained by a binary heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `Heap` interface. (See `Comparable` or `Comparator` for a
 * precise definition of *consistent with equals*.) This is so because
 * the `Heap` interface is defined in terms of the `equals`
 * operation, but a binary heap performs all key comparisons using its
 * `compareTo` (or `compare`) method, so two keys that are deemed
 * equal by this method are, from the standpoint of the binary heap, equal. The
 * behavior of a heap *is* well-defined even if its ordering is
 * inconsistent with `equals`; it just fails to obey the general contract
 * of the `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 *
 * @author Dimitrios Michail
</K> */
class BinaryArrayHeap<K> : AbstractArrayHeap<K> {
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
     * adjusts automatically based on the sequence of insertions and deletions.
     */
    constructor() : super(null, DEFAULT_HEAP_CAPACITY)

    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param capacity
     * the initial heap capacity
     */
    constructor(capacity: Int) : super(null, capacity)

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is
     * [BinaryArrayHeap.DEFAULT_HEAP_CAPACITY] and adjusts automatically
     * based on the sequence of insertions and deletions.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    constructor(comparator: Comparator<in K?>?) : super(comparator, DEFAULT_HEAP_CAPACITY)

    /**
     * Constructs a new, empty heap, with a provided initial capacity ordered
     * according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @param capacity
     * the initial heap capacity
     */
    constructor(comparator: Comparator<in K?>?, capacity: Int) : super(comparator, capacity)

    /**
     * Ensure that the array representation has the necessary capacity.
     *
     * @param capacity
     * the requested capacity
     */
    override fun ensureCapacity(capacity: Int) {
        checkCapacity(capacity)
        val newArray: Array<K?> = arrayOfNulls<Any>(capacity + 1) as Array<K?>
        System.arraycopy(array, 1, newArray, 1, size)
        array = newArray
    }

    override fun fixup(k: Int) {
        var k: Int = k
        val key: K = array[k]!!
        while (k > 1 && (array.get(k shr 1) as Comparable<K>).compareTo(key) > 0) {
            array[k] = array[k shr 1]
            k = k shr 1
        }
        array[k] = key
    }

    override fun fixupWithComparator(k: Int) {
        var k: Int = k
        val key: K = array[k]!!
        while (k > 1 && comparator!!.compare(array[k shr 1], key) > 0) {
            array[k] = array[k shr 1]
            k = k shr 1
        }
        array[k] = key
    }

    override fun fixdown(k: Int) {
        var k: Int = k
        val key: K = array[k]!!
        while (2 * k <= size) {
            var j: Int = 2 * k
            if (j < size && (array.get(j) as Comparable<K>).compareTo(array[j + 1]!!) > 0) {
                j++
            }
            if ((key as Comparable<K>).compareTo(array[j]!!) <= 0) {
                break
            }
            array[k] = array[j]
            k = j
        }
        array[k] = key
    }

    override fun fixdownWithComparator(k: Int) {
        var k: Int = k
        val key: K = array[k]!!
        while (2 * k <= size) {
            var j: Int = 2 * k
            if (j < size && comparator!!.compare(array[j], array[j + 1]) > 0) {
                j++
            }
            if (comparator!!.compare(key, array[j]) <= 0) {
                break
            }
            array[k] = array[j]
            k = j
        }
        array[k] = key
    }

    companion object {

        /**
         * Default initial capacity of the binary heap.
         */
        val DEFAULT_HEAP_CAPACITY: Int = 16

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @return a binary heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @JvmStatic
        @LinearTime
        fun <K> heapify(array: Array<K>?): BinaryArrayHeap<K> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.size == 0) {
                return BinaryArrayHeap()
            }

            val h: BinaryArrayHeap<K> = BinaryArrayHeap(array.size)

            System.arraycopy(array, 0, h.array, 1, array.size)
            h.size = array.size

            for (i in array.size / 2 downTo 1) {
                h.fixdown(i)
            }

            return h
        }

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @param comparator
         * the comparator to use
         * @return a binary heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @LinearTime
        fun <K> heapify(array: Array<K>?, comparator: Comparator<in K?>?): BinaryArrayHeap<K> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.isEmpty()) {
                return BinaryArrayHeap(comparator)
            }

            val h: BinaryArrayHeap<K> = BinaryArrayHeap(comparator, array.size)

            System.arraycopy(array, 0, h.array, 1, array.size)
            h.size = array.size

            for (i in array.size / 2 downTo 1) {
                h.fixdownWithComparator(i)
            }

            return h
        }
    }
}
